package com.demo;

import java.util.Arrays;

/**
 * @author 刘
 */
public class Sort {
    /**
     * 插入排序,将a分为有序a[0],无序a[1-n]两部分
     * 内层循环条件,j>=0;a[j]>tmp(tmp表示待插入元素)
     * 内层循环操作，移动有序部分(寻找插入下标)
     * @param a
     */
    public static void insertSort(int[] a) {
        int n = a.length;
        int i, j, tmp;
        for (i = 1; i < n; i++) {
            tmp = a[i];
            for (j = i - 1; j >= 0 && a[j] > tmp; j--) {
                a[j + 1] = a[j];
            }
            a[j + 1] = tmp;
        }
    }

    public static void selectSort(int[] a){
        int i,j,t;
        int n=a.length;
        for(i=0;i<n;i++){
            for(j=i+1;j<n;j++){
                if(a[i]>a[j]){
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
            }
            System.out.println(Arrays.toString(a));
        }

    }


    public static void bubbleSort(int[] a){
        int i,j,tmp,n=a.length;
        for(i=0;i<n-1;i++){
            for (j=0;j<n-1-i;j++){
                if(a[j]>a[j+1]){
                    tmp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=tmp;
                }
            }
            System.out.println(Arrays.toString(a));
        }
    }

    /**
     * 归并排序：是将两个（或者两个以上）有序表合并成一个新的有序表，
     * 即把待排序序列分为若干个子序列，每个子序列都是有序的。
     * 然后再把有序子序列合并为整体有序序列
     * @param args
     */


    public static void main(String[] args) {
        int[] a={6,13,8,2,9,5,1};
        //Sort.insertSort(a);
        //Sort.selectSort(a);
        Sort.bubbleSort(a);
        //System.out.println(Arrays.toString(a));
    }
}
